/**
 * Copyright 2010 Zhou Zhao
 *
 * This file is part of FPGA compiler for EE680 USC
 *
   FPGA compiler is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation, either version 3 of the License, or
   (at your option) any later version.

   FPGA compiler is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with Foobar.  If not, see <http://www.gnu.org/licenses/>.
 */

/*
 * The class graphTest contains the main function of FPGA compiler.
 * The version 1.0 is not generalized and the test case is a 3*3 CLB
 * array. The coordinates of top-left and buttom-right switchboxes are
 * [0,0] and [6,6], respectively. The capacity of each track is 5. The detail
 * comments are above each methods. Note the FPGA compiler is using JAVA
 * JUNG2 framework for visualization.
 * 
 */

package edu.usc.ee.java;

import edu.uci.ics.jung.algorithms.layout.Layout;
import edu.uci.ics.jung.algorithms.shortestpath.DijkstraShortestPath;
import edu.uci.ics.jung.algorithms.shortestpath.PrimMinimumSpanningTree;
import edu.uci.ics.jung.graph.Graph;
import edu.uci.ics.jung.graph.UndirectedGraph;
import edu.uci.ics.jung.graph.UndirectedSparseGraph;
import edu.uci.ics.jung.visualization.BasicVisualizationServer;
import edu.uci.ics.jung.visualization.renderers.Renderer.VertexLabel.Position;

import java.awt.BasicStroke;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Paint;
import java.awt.Stroke;
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import javax.swing.JFrame;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

import org.apache.commons.collections15.Factory;
import org.apache.commons.collections15.Transformer;

/**
 * @author Zhou Zhao
 * @version 1.0
 */

public class graphTest {

    private Integer N;
    private Integer M;
    private Integer K;
    private Integer T1;
    private Integer T2;
    private Integer T3;
    private Integer T4;
    private Integer LI;
    private Integer SI;

    private UndirectedGraph<switchBox, track> fpga;
    /*
     * TODO generalization start here
     */
    private switchBox[][] n; //swtichbox array
    private track[][] l; //track array
    private Map<Integer, Set<switchBox>> data;
    private boolean flag; //flag to indicate global routing of one net is complete

    //data structure for internal processing
    private List<switchBox> vpath;
    private List<track> epath;
    private Map<Integer, List<switchBox>> vroute;
    private Map<Integer, List<track>> eroute;
    private Map<switchBox, Set<switchBox>> relation;
    private double temperature = 10;

    private Integer[] north;
    private Integer[] south;
    private Integer[] east;
    private Integer[] west;

    //constructor function for initialization
    public graphTest() throws IOException
    {
        Config myConfig = new Config();
        myConfig.configProcess();
        this.N = (myConfig.getCLB()-1)*2+1; //N=9
        this.M = 2*N-1; //M=17
        this.K = myConfig.getIO();
        this.T1 = myConfig.getT1();
        this.T2 = myConfig.getT2();
        this.T3 = myConfig.getT3();
        this.T4 = myConfig.getT4();
        this.LI = myConfig.getLi();
        this.SI = myConfig.getSi();

        this.n = new switchBox[N][N];
        this.l = new track[M][M];
        this.flag = false;
        this.vroute = new HashMap<Integer, List<switchBox>>();
        this.eroute = new HashMap<Integer, List<track>>();
        this.relation = new HashMap<switchBox, Set<switchBox>>();
    }

    public Integer getN(){
        return this.N;
    }

    public Integer getK(){
        return this.K;
    }

    public switchBox getVetex(int x, int y)
    {
        return this.n[x][y];
    }

    public switchBox[][] getn()
    {
        return this.n;
    }

    public track getEdge(int x, int y)
    {
        return this.l[x][y];
    }

    public Map<Integer, Set<switchBox>> getData(){

        return this.data;
    }

    public void setData(Map<Integer, Set<switchBox>> map){

        this.data = map;
    }

    public List<switchBox> getvpath(){
        return this.vpath;
    }

    public List<track> getepath(){
        return this.epath;
    }

    public Map<Integer, List<switchBox>> getvroute(){
        return this.vroute;
    }

    public Map<Integer, List<track>> geteroute(){
        return this.eroute;
    }

    //constructor function to build up the test case
    public void graphConstruct()
    {
        fpga = new UndirectedSparseGraph<switchBox, track>();

        for(int row = 0; row < N; row++){
            for(int column = 0; column < N; column++)
            {
                if (row ==0 || row == N-1)
                {
                    if(column == 0 || column == N-1){
                        n[column][row] = new switchBox(row*N+column, column, row, T3, T1);
                    }else{
                        if(column%2==0){
                            n[column][row] = new switchBox(row*N+column, column, row, T3, T2);
                        }else{
                            n[column][row] = new switchBox(row*N+column, column, row, T3, K);
                        }
                    }
                }
                else
                {
                    if(row%2==0){
                        if(column == 0 || column == N-1){
                            n[column][row] = new switchBox(row*N+column, column, row, T4, T1);
                        }else{
                            if(column%2==0){
                                n[column][row] = new switchBox(row*N+column, column, row, T4, T2);
                            }
                        }
                    }else{
                        if(column == 0){
                            n[column][row] = new switchBox(row*N+column, column, row, K+4, T1);
                        }else{
                            if(column == N-1){
                                n[column][row] = new switchBox(row*N+column, column, row, K+2, T1);
                            }else{
                                if(column%2==0){
                                    n[column][row] = new switchBox(row*N+column, column, row, 6, T2);
                                }
                            }
                        }
                    }
                }
            }
        }

        for(int i=0; i<M; i=i+4){
            if(i==0 || i== M-1){
                for(int j=1; j<M; j=j+2){
                    l[j][i] = new track(i*M+j, j, i, T3);
                    fpga.addEdge(l[j][i], n[(j-1)/2][i/2], n[(j+1)/2][i/2]);
                }
            }else{
                for(int j=2; j<M; j=j+4){
                    l[j][i] = new track(i*M+j, j, i, T4);
                    fpga.addEdge(l[j][i], n[j/2-1][i/2], n[j/2+1][i/2]);
                }
            }
        }

        for(int j=0; j<M; j=j+4){
            if(j==0 || j==M-1){
                for(int i=1; i<M; i=i+2){
                    l[j][i] = new track(i*M+j, j, i, T1);
                    fpga.addEdge(l[j][i], n[j/2][(i-1)/2], n[j/2][(i+1)/2]);
                }
            }else{
                for(int i=1; i<M; i=i+2){
                    l[j][i] = new track(i*M+j, j, i, T2);
                    fpga.addEdge(l[j][i], n[j/2][(i-1)/2], n[j/2][(i+1)/2]);
                }
            }
        }
    }

    //The Dijkstra algorithm based method for finding shortest path from source to target
    public void shortestPath(switchBox nSource, switchBox nTarget)
    {
        Transformer<track, Integer> wtTransformer = new Transformer<track, Integer>()
        {
            public Integer transform(track link)
            {
                return (Integer)link.getWeight();
            }
        };

        DijkstraShortestPath<switchBox, track> alg =
                new DijkstraShortestPath(fpga, wtTransformer);
        List<track> ls = alg.getPath(nSource, nTarget);
        Number dist = alg.getDistance(nSource, nTarget);
        System.out.println("The shortest path from " + nSource.toString()
                + " to " + nTarget.toString() + " is:");
        System.out.println(ls.toString());
        System.out.println("and the length of the path is: " + dist);
    }

    //Prim algorithm based method for finding minimum spanning tree for multi-node global routing
    public void spanningTree()
    {
        Transformer<track, Double> treeTransformer = new Transformer<track, Double>()
        {
            public Double transform(track link)
            {
                Integer wei = new Integer(link.getWeight());
                return new Double(wei.doubleValue());
            }
        };

        Factory<UndirectedGraph<switchBox, track>> treeFactory =
                new Factory<UndirectedGraph<switchBox, track>>() {

            public UndirectedSparseGraph create()
            {
                return new UndirectedSparseGraph<switchBox, track>();
            }
        };

        PrimMinimumSpanningTree<switchBox, track> alg = new PrimMinimumSpanningTree
                (treeFactory, treeTransformer);
        Graph<switchBox, track> prim = alg.transform(fpga);

        System.out.println("The minimum spanning tree of FPGA is:");
        System.out.println(prim.toString());
        
    }

    //congest estimation method between source and target switchboxes
    public void congest(switchBox nSource, switchBox nTarget)
    {
        int xmin = nSource.getx()<=nTarget.getx()? nSource.getx():nTarget.getx();
        int xmax = nSource.getx()>=nTarget.getx()? nSource.getx():nTarget.getx();

        int ymin = nSource.gety()<=nTarget.gety()? nSource.gety():nTarget.gety();
        int ymax = nSource.gety()>=nTarget.gety()? nSource.gety():nTarget.gety();

        int weight;

        for(int row = ymin; row <= ymax; row++){
            for(int column = xmin; column <= xmax; column++)
            {

                if (row == 0 || row == N-1)
                {
                    weight = n[column][row].getWeight();
                    n[column][row].setWeight(++weight);
//                    n[column][row].setColor(myColor.BLUE);
                }
                else
                {
                    if (column%2 == 0)
                    {
                        weight = n[column][row].getWeight();
                        n[column][row].setWeight(++weight);
//                        n[column][row].setColor(myColor.BLUE);
                    }
                }
            }
        }
    }

    //overloaded congest method which can process the set of switchboxes
    public void congest(Set<switchBox> vset)
    {
        int xmin, xmax, ymin, ymax;
        int weight;
        switchBox[] a = vset.toArray(new switchBox[0]);

        xmin = a[0].getx();
        xmax = xmin;
        ymin = a[0].gety();
        ymax = ymin;
        for(int i=1; i<a.length; i++){
            xmin = a[i].getx()<xmin? a[i].getx():xmin;
            xmax = a[i].getx()>xmax? a[i].getx():xmax;
            ymin = a[i].gety()<ymin? a[i].gety():ymin;
            ymax = a[i].gety()>ymax? a[i].gety():ymax;
        }

//        System.out.println("xmin:"+xmin+" xmax:"+xmax+" ymin:"+ymin+" ymax:"+ymax);
        for(int row = ymin; row <= ymax; row++){
            for(int column = xmin; column <= xmax; column++)
            {

                if (row == 0 || row == N-1)
                {
                    weight = n[column][row].getWeight();
                    n[column][row].setWeight(++weight);
//                    n[column][row].setColor(myColor.BLUE);
                }
                else
                {
                    if (column%2 == 0)
                    {
                        weight = n[column][row].getWeight();
                        n[column][row].setWeight(++weight);
//                        n[column][row].setColor(myColor.BLUE);
                    }
                }
            }
        }
    }

    //give one parent switchbox, the method can find its adjacent children
    public Map<switchBox, Set<switchBox>> findChildren(switchBox parent){

        Set<switchBox> children = new HashSet<switchBox>();
        Map<switchBox, Set<switchBox>> group = new HashMap<switchBox, Set<switchBox>>();
        int x = parent.getx();
        int y = parent.gety();

        if(y==0){
            if(x==0){
                children.add(n[x+1][y]);
                children.add(n[x][y+1]);
            }else{
                if(x==N-1){
                    children.add(n[x-1][y]);
                    children.add(n[x][y+1]);
                }else{
                    if(x%2==0){
                        children.add(n[x-1][y]);
                        children.add(n[x+1][y]);
                        children.add(n[x][y+1]);
                    }else{
                        children.add(n[x-1][y]);
                        children.add(n[x+1][y]);
                    }
                }
            }

        }else{
            if(y==N-1){
                if(x==0){
                    children.add(n[x+1][y]);
                    children.add(n[x][y-1]);
                }else{
                    if(x==N-1){
                        children.add(n[x-1][y]);
                        children.add(n[x][y-1]);
                    }else{
                        if(x%2==0){
                            children.add(n[x-1][y]);
                            children.add(n[x+1][y]);
                            children.add(n[x][y-1]);
                        }else{
                            children.add(n[x-1][y]);
                            children.add(n[x+1][y]);
                        }
                    }
                }
            }else{
                if(y%2==0){
                    if(x==0){
                        children.add(n[x][y-1]);
                        children.add(n[x][y+1]);
                        children.add(n[x+2][y]);
                    }else{
                        if(x==N-1){
                            children.add(n[x][y-1]);
                            children.add(n[x][y+1]);
                            children.add(n[x-2][y]);
                        }else{
                            if(x%2==0){
                                children.add(n[x-2][y]);
                                children.add(n[x+2][y]);
                                children.add(n[x][y-1]);
                                children.add(n[x][y+1]);
                            }else{
                                System.out.println("invalid x="+x+" y="+y);
                            }
                        }
                    }
                }else{
                    if(x%2==0){
                        children.add(n[x][y-1]);
                        children.add(n[x][y+1]);
                    }else{
                        System.out.println("invalid x="+x+" y="+y);
                    }
                }
            }

        }

        group.put(parent, children);
        return group;
        
    }

    //the method compute weight for each switchbox according to the equation
    //Label(grid cell) = MIN(weight(parent grid cell)+weight(grid cell))
    public void weightCompute(Map<switchBox, Set<switchBox>> group){

        Set<switchBox> key = group.keySet();

        for(switchBox i: key){
            for(switchBox j: group.get(i)){
                if(!j.getUpdate()){
                    j.setWeightWave(i.getWeightWave()+j.getWeight()+1);
                    j.setUpdate(true);
                }else{

                    if(i.getWeightWave()+j.getWeight()+1<j.getWeightWave()){
                        j.setWeightWave(i.getWeightWave()+j.getWeight()+1);
                    }
                }
//                System.out.println(j);
            }
        }
    }

    //method to find the child switchbox with minimum weight around specified parent switchbox
    public switchBox minCompute(Map<switchBox, Set<switchBox>> group){

        Set<switchBox> key = group.keySet();
        switchBox [] a;
        switchBox min = new switchBox();

        for(switchBox i: key){
            Set<switchBox> value = group.get(i);
            a = value.toArray(new switchBox[0]);
            min = a[0];
            
            for(switchBox j: value){
                min = j.getWeightWave()<min.getWeightWave()? j:min;
            }

            //System.out.println("the min vertex around "+i+" is "+min);
        }

        return min;

    }

    //method to propagate the wave in Lee's algorithm without both parent and updated node
    public Map<switchBox, Set<switchBox>> direction1(switchBox parent, switchBox child){
        //filter some elements from set
        Map<switchBox, Set<switchBox>> grandchild = new HashMap<switchBox, Set<switchBox>>();
        Map<switchBox, Set<switchBox>> grand = new HashMap<switchBox, Set<switchBox>>();

        grandchild = findChildren(child);
        grand = findChildren(child);

        Set<switchBox> key = grandchild.keySet();

        for(switchBox i: key){
                if(!grand.get(i).remove(parent)){
                    System.out.println("invalid parent or child");
                }
                for(switchBox j: grandchild.get(i)){
                    if(j.getUpdate()){
                        grand.get(i).remove(j);
                    }
                }
        }

        return grand;
    }

    //another method to propagate the wave in Lee's algorithm without parent
    public Map<switchBox, Set<switchBox>> direction2(switchBox parent, switchBox child){
        //filter some elements from set
        Map<switchBox, Set<switchBox>> grandchild = new HashMap<switchBox, Set<switchBox>>();
        Map<switchBox, Set<switchBox>> grand = new HashMap<switchBox, Set<switchBox>>();

        grandchild = findChildren(child);
        grand = findChildren(child);

        Set<switchBox> key = grandchild.keySet();

        for(switchBox i: key){
                if(!grand.get(i).remove(parent)){
                    System.out.println("invalid parent or child");
                }
        }

        return grand;
    }

    //weighted Lee's algorithm to find path between source and target with breadth-first-search
    public void waveCompute(switchBox source, switchBox target)
    {
        Map<switchBox, Set<switchBox>> group = new HashMap<switchBox, Set<switchBox>>();       
        Queue<List<switchBox>> q = new LinkedList<List<switchBox>>();
        source.setWeightWave(source.getWeight());

        group = findChildren(source);
        Set<switchBox> key = group.keySet();
        weightCompute(group);

        for(switchBox i: key){
            for(switchBox j: group.get(i)){
                List<switchBox> pair = new ArrayList<switchBox>();
                pair.add(0, i);
                pair.add(1, j);
                q.add(pair);
            }
        }

        while(!q.isEmpty()){

        List<switchBox> head = q.remove();
        switchBox key1 = head.get(0);
        switchBox value1 = head.get(1);

        if(key1.equals(target)){
            q.clear();
        }else{

        
        
        group = direction1(key1, value1);
        Set<switchBox> key2 = group.keySet();
        
        for(switchBox i: key2){
            for(switchBox j: group.get(i)){
                List<switchBox> pair = new ArrayList<switchBox>();
                pair.add(0, i);
                pair.add(1, j);
                q.add(pair);
            }
        }
        
        group = direction2(key1, value1);
        weightCompute(group);

        }
        }
    }

    //backTrack method is calling recursive method "recursive" to find path with monotonically
    //decreasing weight
    public void backTrack(switchBox source, switchBox target){

        vpath = new ArrayList<switchBox>();
        epath = new ArrayList<track>();

        switchBox m = recursive(source, target);
        vpath.add(m);
        vpath.add(target);
        epath.add(getEdge(m.getx()+target.getx(), m.gety()+target.gety()));
        
//        System.out.println(vpath);
//        System.out.println(epath);

    }

    public switchBox recursive(switchBox source, switchBox target){
        
        Map<switchBox, Set<switchBox>> group = new HashMap<switchBox, Set<switchBox>>();
        group = findChildren(target);
        switchBox m = minCompute(group);

        if(!m.equals(source)){
            switchBox r = recursive(source, m);
            vpath.add(r);
            int x = m.getx()+r.getx();
            int y = m.gety()+r.gety();
            epath.add(getEdge(x, y));
        }

        return m;
    }

    public void updateSwitchBox(List<switchBox> path){

        for(int i=0; i<path.size(); i++){
            switchBox t = path.get(i);
            t.setWeight(t.getWeight()+1);
        }
    }

    //method to estimate congestion, if track capacity is overflowed
    public void updateTrack(List<track> path){

        for(int i=0; i<path.size(); i++){
            track t = path.get(i);
            t.setCapacity(t.getCapacity()+1);
        }
    }

    //clean up method
    public void waveClear(){
        for(int row = 0; row < N; row++){
            for(int column = 0; column < N; column++)
            {
                if (row == 0 || row == N-1)
                {
                    n[column][row].setWeightWave(0);
                    n[column][row].setUpdate(false);
                }
                else
                {
                    if (column%2 == 0)
                    {
                        n[column][row].setWeightWave(0);
                        n[column][row].setUpdate(false);
                    }
                }
            }
        }
    }

    public void weightClear(){
        for(int row = 0; row < N; row++){
            for(int column = 0; column < N; column++)
            {
                if (row == 0 || row == N-1)
                {
                    n[column][row].setWeight(0);
                }
                else
                {
                    if (column%2 == 0)
                    {
                        n[column][row].setWeight(0);
                    }
                }
            }
        }
    }


    public void congestRoute(){

        Set<Integer> signal = vroute.keySet();

        for(Integer i: signal){
            for(switchBox j: vroute.get(i)){
                j.setWeight(j.getWeight()+1);
            }
        }
    }

    //global initial route
    public void initialRoute(){
    
        switchBox[] path;

        Set<Integer> keyset = data.keySet();

        Map<Integer, List<switchBox>> vcomp = new HashMap<Integer, List<switchBox>>();
        Map<Integer, List<track>> ecomp = new HashMap<Integer, List<track>>();
        Set<Integer> length;

        Integer[] len;
        boolean swap = false;
        Integer temp;

        List<switchBox> vbuffer;
        List<track> ebuffer;

        for(Integer i: keyset){
            Set<switchBox> value = data.get(i);
            if(value.size()==2){
//                System.out.println("signal "+i+": "+value);
                path = value.toArray(new switchBox[0]);
                congest(path[0], path[1]);
            }else{
                congest(value);
            }
        }

        for(Integer j: keyset){
            Set<switchBox> value = data.get(j);

            if(value.size()==2){
            System.out.println("2 node signal "+j+" is routed globally");
            path = value.toArray(new switchBox[0]);
            waveCompute(path[0], path[1]);
            backTrack(path[0], path[1]);
            vroute.put(j, vpath);
            eroute.put(j, epath);
            waveClear();
            updateTrack(epath);

            }else{
        //routine for multi-point global route
                if(value.size()==3){
                    System.out.println("3 node signal "+j+" is routed globally");
                    path = value.toArray(new switchBox[0]);
                    waveCompute(path[0], path[1]);
                    backTrack(path[0], path[1]);
                    vcomp.put(1, vpath);
                    ecomp.put(1, epath);
                    waveClear();

                    waveCompute(path[0], path[2]);
                    backTrack(path[0], path[2]);
                    vcomp.put(2, vpath);
                    ecomp.put(2, epath);
                    waveClear();

                    waveCompute(path[1], path[2]);
                    backTrack(path[1], path[2]);
                    vcomp.put(3, vpath);
                    ecomp.put(3, epath);
                    waveClear();

                    length = vcomp.keySet();
                    len = length.toArray(new Integer[0]);
                    while(!swap){
                        swap = true;
                        for(int i=0; i<len.length-2; i++){
                            if(vcomp.get(len[i]).size() > vcomp.get(len[i+1]).size()){
                                temp = len[i];
                                len[i] = len[i+1];
                                len[i+1] = temp;
                                swap = false;
                            }
                        }
                    }

                    vbuffer = new ArrayList<switchBox>();
                    vbuffer.addAll(vcomp.get(len[0]));
                    for(switchBox i: vcomp.get(len[1])){
                        if(!vbuffer.contains(i)){
                            vbuffer.add(i);
                        }
                    }
                    vroute.put(j, vbuffer);
                    System.out.println(vbuffer);

                    ebuffer = new ArrayList<track>();
                    ebuffer.addAll(ecomp.get(len[0]));
                    for(track k: ecomp.get(len[1])){
                        if(!ebuffer.contains(k)){
                            ebuffer.add(k);
                        }
                    }
                    eroute.put(j, ebuffer);
                    updateTrack(ebuffer);
                }
            }
        }
    }

    public int congestCount(){
        int count = 0;

        for(int i=0; i<M; i=i+4){
            if(i==0 || i== M-1){
                for(int j=1; j<M; j=j+2){
                    if(l[j][i].getCapacity()>l[j][i].getWeight()){
                        count++;
                    }
                }
            }else{
                for(int j=2; j<M; j=j+4){
                    if(l[j][i].getCapacity()>l[j][i].getWeight()){
                        count++;
                    }
                }
            }
        }

        for(int j=0; j<M; j=j+4){
            if(j==0 || j==M-1){
                for(int i=1; i<M; i=i+2){
                    if(l[j][i].getCapacity()>l[j][i].getWeight()){
                        count++;
                    }
                }
            }else{
                for(int i=1; i<M; i=i+2){
                    if(l[j][i].getCapacity()>l[j][i].getWeight()){
                        count++;
                    }
                }
            }
        }
        
        return count;
    }

    public void ripup(Integer net){

        System.out.println("The signal "+net+" is ripup");

        if(vroute.containsKey(net)){
            for(switchBox j: vroute.get(net)){
                j.setWeight(j.getWeight()-1);
            }
        }else{
            System.out.println("The signal "+net+" is not routed in vroute");
        }

        if(eroute.containsKey(net)){
            for(track k: eroute.get(net)){
                k.setCapacity(k.getCapacity()-1);
            }
        }else{
            System.out.println("The signal "+net+" is not routed in eroute");
        }
    }

    //global re-route
    public void reRoute(int r){

        switchBox[] path;

        Map<Integer, List<switchBox>> vcomp = new HashMap<Integer, List<switchBox>>();
        Map<Integer, List<track>> ecomp = new HashMap<Integer, List<track>>();
        Set<Integer> length;

        Integer[] len;
        boolean swap = false;
        Integer temp;

        List<switchBox> vbuffer = new ArrayList<switchBox>();
        List<track> ebuffer = new ArrayList<track>();
        
        if(vroute.containsKey(r)){
            Set<switchBox> value = data.get(r);
            if(value.size()==2){
            System.out.println("2 node signal "+r+" is re-routed");

                path = value.toArray(new switchBox[0]);
                waveCompute(path[0], path[1]);
                backTrack(path[0], path[1]);
                vroute.put(r, vpath);
                eroute.put(r, epath);
                waveClear();
                updateSwitchBox(vpath);
                updateTrack(epath);
            }else{
                //routine for multi-point global route
                if(value.size()==3){
                    System.out.println("3 node signal "+r+" is re-routed");
                    path = value.toArray(new switchBox[0]);
                    waveCompute(path[0], path[1]);
                    backTrack(path[0], path[1]);
                    vcomp.put(1, vpath);
                    ecomp.put(1, epath);
                    waveClear();

                    waveCompute(path[0], path[2]);
                    backTrack(path[0], path[2]);
                    vcomp.put(2, vpath);
                    ecomp.put(2, epath);
                    waveClear();

                    waveCompute(path[1], path[2]);
                    backTrack(path[1], path[2]);
                    vcomp.put(3, vpath);
                    ecomp.put(3, epath);
                    waveClear();                   

                    length = vcomp.keySet();
                    len = length.toArray(new Integer[0]);
                    while(!swap){
                        swap = true;
                        for(int i=0; i<len.length-2; i++){
                            if(vcomp.get(len[i]).size() > vcomp.get(len[i+1]).size()){
                                temp = len[i];
                                len[i] = len[i+1];
                                len[i+1] = temp;
                                swap = false;
                            }
                        }
                    }

                    vbuffer.addAll(vcomp.get(len[0]));
                    for(switchBox i: vcomp.get(len[1])){
                        if(!vbuffer.contains(i)){
                            vbuffer.add(i);
                        }
                    }
                    vroute.put(r, vbuffer);
                    updateSwitchBox(vbuffer);
                    System.out.println(vbuffer);

                    ebuffer.addAll(ecomp.get(len[0]));
                    for(track k: ecomp.get(len[1])){
                        if(!ebuffer.contains(k)){
                            ebuffer.add(k);
                        }
                    }
                    eroute.put(r, ebuffer);
                    updateTrack(ebuffer);
                }

            }
        }else{
            System.out.println("The signal"+r+" is not routed");
        }
    }

public boolean anneal(int d){

    if (temperature < 1.0E-4) {
      if (d > 0)
        return true;
      else
        return false;
    }

    if (Math.random() < Math.exp(d / temperature))
      return true;
    else
      return false;
    }

    /*
     * method for simulated annealing
     */
    public boolean sa()
  {
    int cycle = 1;
    int step = 1;
    int sameCount = 0;
    int acceptCount = 0;
    int rejectCount = 0;

    Map<Integer, List<switchBox>> vroute_copy = new HashMap<Integer, List<switchBox>>();
    Map<Integer, List<track>> eroute_copy = new HashMap<Integer, List<track>>();
    Set<Integer> keyset = vroute.keySet();
    Integer[] key = keyset.toArray(new Integer[0]);
    int len = key.length;

    vroute_copy.putAll(vroute);
    eroute_copy.putAll(eroute);

    int present_congest = congestCount();
    int minimum_congest = present_congest;

    while (sameCount < 10) {
      // update the screen
      for (int i = 0; i < len*len; i++){

        int signal = (int)Math.floor((double)len * Math.random());
        ripup(key[signal]);
        reRoute(key[signal]);
        int temp = congestCount();
        System.out.println("The number of congested wires = "+temp);
        int delta = present_congest - temp;

        if (anneal(delta)){
            acceptCount++;
            vroute_copy.putAll(vroute);
            eroute_copy.putAll(eroute);
            present_congest = temp;
        }else{
            rejectCount++;
            vroute.putAll(vroute_copy);
            eroute.putAll(eroute_copy);
        }

        step++;
      }

      // See if this improved anything
      int final_congest = present_congest;
      if (final_congest < minimum_congest){
          minimum_congest = final_congest;
          sameCount=0;
      }else{
          sameCount++;
          temperature = 0.9 * temperature;
          cycle++;
      }

      System.out.println("sameCount="+sameCount+" cycle="+cycle);
    }

    // the process of simulated annealing is complete
    if(congestCount()==0){
        System.out.println("Solution found after " + cycle + " cycles.");
        System.out.println("step="+step+" accept="+acceptCount+" reject="+rejectCount);
        System.out.println("\nThe global final routing is");
        System.out.println(vroute);
//    System.out.println(eroute);
        return true;
    }else{
        System.out.println("The netlist can not be routed");
        return false;
    }
    }

    public void switchBoxConfig(){

        Set<Integer> signal = vroute.keySet();
        int k;

        for(Integer i: signal){
            switchBox[] temp = vroute.get(i).toArray(new switchBox[0]);
            k = temp.length;

            switchBoxComp(i, temp[1], temp[0]);

            for(int j=1; j<k-1; j++){
                switchBoxComp(i, temp[j-1], temp[j]);
                switchBoxComp(i, temp[j+1], temp[j]);
            }

            switchBoxComp(i, temp[k-2], temp[k-1]);
        }
    }

    public void switchBoxComp(Integer net, switchBox vpn, switchBox vc){

        switch (vpn.getx()-vc.getx()){
            case -2: vc.addWest(net); break;
            case -1: vc.addWest(net); break;
            case 0: break;
            case 1: vc.addEast(net); break;
            case 2: vc.addEast(net); break;
            default: System.out.println("invalid x along signal "+net+" at "+vc); break;
        }

        switch (vpn.gety()-vc.gety()){
            case -1: vc.addNorth(net); break;
            case 0: break;
            case 1: vc.addSouth(net); break;
            default: System.out.println("invalid y along signal "+net+" at "+vc); break;
        }
    }

    public void debug(int row, int column, int row_max, int column_max) throws IOException{

        List<Integer> nor = n[column][row].getNorth();
        List<Integer> sou = n[column][row].getSouth();
        List<Integer> eas = n[column][row].getEast();
        List<Integer> wes = n[column][row].getWest();

        int count = nor.size();
        for(int i=0; i<column_max-count; i++){
            nor.add(0);
        }

        count = sou.size();
        for(int i=0; i<column_max-count; i++){
            sou.add(0);
        }

        count = eas.size();
        for(int j=0; j<row_max-count; j++){
            eas.add(0);
        }

        count = wes.size();
        for(int j=0; j<row_max-count; j++){
            wes.add(0);
        }

        north = nor.toArray(new Integer[0]);
        south = sou.toArray(new Integer[0]);
        east = eas.toArray(new Integer[0]);
        west = wes.toArray(new Integer[0]);
    }

    public void ouputFile(){
        try{
            BufferedWriter out = new BufferedWriter(new FileWriter("output.txt", true));
            out.write("Setting\n{\nLiCount="+LI+"\nSiCount="+SI+"\nn="+((N-1)/2+1)+"\nk="+K);
            out.write("\nT1="+T1+"\nT2="+T2+"\nT3="+T3+"\nT4="+T4+"\n}\n");
            out.close();
        }catch (IOException e){

        }
    }

    //global routing main method
    public void globalRoute() throws IOException{

        System.out.println("FPGA config file is processed...");

        System.out.println("\n\nFPGA graph model is under constructing...");
        Netlist net = new Netlist((N-1)/2, K);
        graphConstruct();

        System.out.println("\n\nNetlist file is imported...");
        setData(net.netlistProcess(getn()));
        System.out.println(getData());

        System.out.println("\n\nInitial routing is starting...");
        initialRoute();
        weightClear();
        congestRoute();
        System.out.println("\n\nAfter initial routing, the number of congested track = "+congestCount());

        System.out.println("\n\nSimulated annealing is starting...");
        if(sa()){
            System.out.println("\n\nSwitchBox is under configuration...");
            switchBoxConfig();
            ouputFile();
            for(int row = 0; row < N; row++){
            for(int column = 0; column < N; column++)
            {
                if (row ==0 || row == N-1)
                {
                    if(column == 0 || column == N-1){
                        debug(row, column, T3, T1);
                        switchboxRouter mb = new switchboxRouter(T3, T1, 1, column, row, north, south, east, west);
                        mb.detailRoute();
                    }else{
                        if(column%2==0){
                            debug(row, column, T3, T2);
                            switchboxRouter mb = new switchboxRouter(T3, T2, 2, column, row, north, south, east, west);
                            mb.detailRoute();
                        }else{
                            debug(row, column, T3, K);
                            switchboxRouter mb = new switchboxRouter(T3, K, 3, column, row, north, south, east, west);
                            mb.detailRoute();
                        }
                    }
                }
                else
                {
                    if(row%2==0){
                        if(column == 0 || column == N-1){
                            debug(row, column, T4, T1);
                            switchboxRouter mb = new switchboxRouter(T4, T1, 7, column, row, north, south, east, west);
                            mb.detailRoute();
                        }else{
                            if(column%2==0){
                                debug(row, column, T4, T2);
                                switchboxRouter mb = new switchboxRouter(T4, T2, 8, column, row, north, south, east, west);
                                mb.detailRoute();
                            }
                        }
                    }else{
                        if(column == 0){
                            debug(row, column, K+4, T1);
                            switchboxRouter mb = new switchboxRouter(K+4, T1, 4, column, row, north, south, east, west);
                            mb.detailRoute();
                        }else{
                            if(column == N-1){
                                debug(row, column, K+2, T1);
                                switchboxRouter mb = new switchboxRouter(K+2, T1, 5, column, row, north, south, east, west);
                                mb.detailRoute();
                            }else{
                                if(column%2==0){
                                    debug(row, column, 6, T2);
                                    switchboxRouter mb = new switchboxRouter(6, T2, 6, column, row, north, south, east, west);
                                    mb.detailRoute();
                                }
                            }
                        }
                    }
                }
            }
        }
        }

        
//-----------------------following code is for visualization--------------------
        
        Layout<switchBox, track> layout = new XYLayout(fpga);
        layout.setSize(new Dimension(N*100, N*100));
        BasicVisualizationServer<switchBox, track> vs = new BasicVisualizationServer
                <switchBox, track>(layout);
        vs.setPreferredSize(new Dimension(N*100+50, N*100+50));

        Transformer<switchBox, Paint> vertex2paint = new Transformer<switchBox, Paint>() {

            public Paint transform(switchBox i) {
               switch(i.getColor())
               {
                   case RED: return Color.RED;
                   case GREEN: return Color.GREEN;
                   case BLUE: return Color.BLUE;
                   case YELLOW: return Color.YELLOW;
                   default: return Color.BLACK;
               }
            }
        };

        float dash[] = {10.0f};
        final Stroke edgeStroke =
                new BasicStroke(1.0f, BasicStroke.CAP_BUTT, BasicStroke.JOIN_MITER,
                10.0f, dash, 0.0f);
        Transformer<track, Stroke> edge2stroke = new Transformer<track, Stroke>() {

            public Stroke transform(track i) {
                return edgeStroke;
            }
        };

        Transformer<switchBox, String> vertex2string = new Transformer<switchBox, String>() {

            public String transform(switchBox i) {
//                return i.getID()+"("+i.getx()+","+i.gety()+")";
//                return i.getWeight()+","+i.getWeightWave();
//                return "N"+i.getNorth()+"S"+i.getSouth()+"E"+i.getEast()+"W"+i.getWest();
//                return "N"+i.getNorth();
                return "E"+i.getEast();
            }
        };

        Transformer<track, String> edge2string = new Transformer<track, String>() {

            public String transform(track i) {
//                return i.getID()+"("+i.getx()+","+i.gety()+")";
                return i.getCapacity()+","+i.getWeight();
            }
        };
        
          vs.getRenderContext().setVertexFillPaintTransformer(vertex2paint);
//        vs.getRenderContext().setVertexLabelTransformer(new ToStringLabeller());
          vs.getRenderContext().setVertexLabelTransformer(vertex2string);
          vs.getRenderer().getVertexLabelRenderer().setPosition(Position.CNTR);

//        vs.getRenderContext().setEdgeLabelTransformer(new ToStringLabeller());
          vs.getRenderContext().setEdgeLabelTransformer(edge2string);
//        vs.getRenderContext().setEdgeStrokeTransformer(edge2stroke);

        JFrame frame = new JFrame("FPGA Global Model");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.getContentPane().add(vs);
        frame.pack();
        frame.setVisible(true);
        
/*
        System.out.println("The graph model of fpga: " + myGraph.fpga.toString());
        myGraph.shortestPath();
        myGraph.spanningTree();
 *
 */
    } 
}
